/**
 * 当差数列求和公式 (首项+末相项)*项数/2
 */
class ArraryList {
	constructor() {
		this.arr = []
	}
	insert(val) {
		this.arr.push(val)
	}
	toString() {
		return this.arr.join(' ')
	}
}
let that
class Sort extends ArraryList {
	constructor() {
		super()
		that = this
	}
	/**
	 * 冒泡排序
	 * 每一轮 通过两两比较 把最大的数放到最后
	 * 比较次数 n*(1+n-1)/2   O(n^2)
	 * 交换次数  比较次数/2  n*(1+n-1)/4   O(n^2)
	 *
	 */
	bubbleSort() {
		let arr = that.init()
		const len = arr.length - 1
		// // 第一种  小白遍历思想 不考虑任何情况
		// for (let i = 0; i < len; i++) {
		// 	// 比较 i 和 i+1 的大小
		// 	for (let j = 0; j < len; j++) {
		// 		if (arr[j] > arr[j + 1]) {
		// 			// 交换顺序 抽取成函数
		// 			this.swap(j, j + 1)
		// 		}
		// 	}
		// }

		//第二种  菜鸟遍历思想 考虑边界但不考虑特殊情况
		// for (let i = 0; i < len; i++) {
		// 	// 比较 i 和 i+1 的大小
		// 	for (let j = 0; j < len - i; j++) {
		// 		if (arr[j] > arr[j + 1]) {
		// 			this.swap(j, j + 1)
		// 		}
		// 	}
		// }

		// 第三种 高水平 考虑各种情况进行优化
		//算法优化1,如果第一次走完都没有交换说明数据是有序的 无需进行排序
		//算法优化2,如果其中一次走完都没有交换说明此时数据是有序的 无需进行排序,
		// 其实算法2已经包含算法1了,只不过可能会想不到算法2的优化
		for (let i = len; i > 0; i--) {
			let flag = true //每一次循环就开启一个标志，当前循环完后没有交换 说明已经排序好了
			for (let j = 0; j < i; j++) {
				if (arr[j] > arr[j + 1]) {
					this.swap(j, j + 1)
					flag = false
				}
			}
			// 每一轮循环都会判断当前数组是否已经排序好了
			// flag 为true  说明数据是有序的 无需进行排序了
			// flag 为false 说明数据进行了一次交换  无法判断数据是否已经排序好了，所以要开启下一轮循环
			if (flag) {
				break
			}
		}
		return arr
	}
	/**
	 * 选择排序
	 * 1. 每一轮都 找到最小的值（与 第i位 交换位置）
	 * 比较次数 n*(1+n-1)/2  O(n^2)
	 * 交换次数  n-1 次 O(n)
	 *
	 */
	selectionSort() {
		let arr = that.init()
		let minIndex = 0 // 记录一轮查找最小值的下标
		for (var i = 0; i < arr.length - 1; i++) {
			minIndex = i // 最小值的下标 每一轮循环都会找到一个最小的值 替换掉arr[i]的值
			for (var j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[minIndex]) {
					minIndex = j
				}
			}
			this.swap(minIndex, i)
		}
	}
	/**
	 * 插入排序
	 * 1. 将数据分为有序和无序两个部分 从下标 1 开始
	 * 2. 在无序中选择第一个 插入到有序的对应位置 (移动)
	 * 比较次数 n*(1+n-1)/4  O(n^2)
	 * 复制次数   n*(1+n-1)/4
	 */
	insertionSort() {
		let arr = that.init()
		let len = arr.length
		let preIndex, curdata
		for (let i = 1; i < len; i++) {
			preIndex = i - 1
			curdata = arr[i] // 保存要比对的数
			while (curdata < arr[preIndex] && preIndex >= 0) {
				arr[preIndex + 1] = arr[preIndex] //数据后移一位
				preIndex--
			}
			// preIndex == -1 或者等于 i - 1
			arr[preIndex + 1] = curdata
		}
		return arr
	}
	/**
	 * 希尔排序 利用间隔分组
	 * 在插入排序的基础上添加一个组的规则
	 */
	shellSort() {
		let arr = that.init()
		let len = arr.length
		// 1.定义间隔
		let gap = Math.floor(len / 2)
		// 2. 停止排序
		while (gap > 0) {
			// 3. 分组
			for (let i = gap; i < len; i++) {
				// 4. 插入排序过程
				let preIndex = i - gap
				let curdata = arr[i]
				while (curdata < arr[preIndex] && preIndex >= 0) {
					arr[preIndex + gap] = arr[preIndex]
					preIndex -= gap
				}
				arr[preIndex + gap] = curdata
			}
			// 改变分组间隔
			gap = Math.floor(gap / 2)
		}
	}
	/**
	 * 快速排序 分而治之
	 *
	 */
	quicksort() {
		let arr = that.init()
		let len = arr.length
		this.quick(0, len - 1)
		return arr
	}
	// 快速排序辅助函数 找枢纽
	partition(left, right) {
		const center = Math.floor((left + right) / 2)
		// 冒泡排序思想
		if (this.arr[left] > this.arr[center]) {
			this.swap(left, center)
		}
		if (this.arr[center] > this.arr[right]) {
			this.swap(center, right)
		}
		if (this.arr[left] > this.arr[center]) {
			this.swap(left, center)
		}
		this.swap(center, right - 1)
		return this.arr[right - 1]
	}
	// 快速排序辅助函数 递归排序
	quick(left, right) {
		if (left >= right) return
		let pivot = this.partition(left, right)
		let i = left
		let j = right - 1
		while (i < j) {
			while (this.arr[++i] < pivot) {}
			while (this.arr[--j] > pivot) {}
			if (i < j) {
				this.swap(i, j)
			}
		}
		this.swap(i, right - 1)
		this.quick(left, i - 1)
		this.quick(i + 1, right)
	}
	// 封装公共代码片段
	init() {
		let arr = that.arr
		const len = arr.length - 1
		if (!arr.length) return
		if (arr.length == 1) return arr[0]
		return arr
	}
	// 抽取交换方法
	swap(m, n) {
		let temp = this.arr[m]
		this.arr[m] = this.arr[n]
		this.arr[n] = temp
	}
}

let sort = new Sort()
sort.insert(66)
sort.insert(88)
sort.insert(12)
sort.insert(87)
sort.insert(100)
sort.insert(5)
sort.insert(566)

// sort.insert(1)
// sort.insert(10)
// sort.insert(111)
// sort.insert(11)
// sort.insert(12)

console.log('原始数据', sort.toString())

// console.time('bubbleSort')
// sort.bubbleSort()
// console.timeEnd('bubbleSort')
// console.log('冒泡排序', sort.toString())

// console.time('selectionSort')
// sort.selectionSort()
// console.timeEnd('selectionSort')
// console.log('选择排序', sort.toString())

// console.time('insertionSort')
// sort.insertionSort()
// console.timeEnd('insertionSort')
// console.log('插入排序', sort.toString())

// console.time('shellSort')
// sort.shellSort()
// console.timeEnd('shellSort')
// console.log('希尔排序', sort.toString())

console.time('quicksort')
sort.quicksort()
console.timeEnd('quicksort')
console.log('快速排序', sort.toString())
